﻿#define  _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

using namespace std;

namespace zl
{
	//搜索二叉树  O(n)
	//root->left<root&&root->right>root
	//Node
	//kv
	template <class K,class V>
	struct BSTreeNode
	{
		typedef BSTreeNode<K,V> Node;


		Node* _left;
		Node* _right;
		K _key;
		V _value;

		//初始化
		BSTreeNode(const K& key,const V& value)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			,_value(value)
		{}



	};


	//Tree
	template <class K,class V>
	class BSTree
	{
	public:
		typedef BSTreeNode<K,V> Node;

		//强制生成默认构造
		BSTree() = default;

		BSTree(const BSTree<K, V>& t)
		{
			_root = Copy(t._root);
		}

		BSTree<K,V>& operator=(const BSTree<K, V>& t)
		{
			swap(_root, t._root);

			return *this;
		}

		~BSTree()
		{
			Destroy(_root);
		}


		//插入
		bool Insert(const K& key, const V& value)
		{
			//检查是否有根节点
			if (_root == nullptr)
			{
				_root = new Node(key,value);
				return true;
			}


			Node* prev = nullptr;//cur的父亲
			Node* cur = _root;//从根节点开始

			//找到插入位置
			while (cur != nullptr)
			{
				//小于
				if (key < cur->_key)
				{
					prev = cur;
					cur = cur->_left;
				}
				//大于
				else if (key > cur->_key)
				{
					prev = cur;
					cur = cur->_right;
				}
				//找不到了
				else
				{
					return false;
				}
			}

			//链接
			//此时cur是null
			cur = new Node(key,value);
			if (prev->_key > cur->_key)
			{
				prev->_left = cur;
			}
			else
			{
				prev->_right = cur;
			}

			return true;

		}

		//中序遍历打印（递归）
		// 从大到小
		//封装一下，不用传root
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

		//查找
		bool Find(const K& key)
		{
			Node* cur = _root; // 从根结点开始查找

			while (cur != nullptr)
			{
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else  if (cur->_key > key)
				{
					cur = cur->_left;
				}
				else
				{
					return true;
				}
			}


			return false;
		}

		//删除
		bool Erase(const K& key)
		{
			Node* father = nullptr;
			Node* cur = _root;

			//查找
			while (cur)
			{
				if (cur->_key < key)
				{
					father = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					father = cur;
					cur = cur->_left;
				}
				else
				{
					//找到了   
					//情况一：该节点没有左孩子
					if (cur->_left = nullptr)
					{
						/* 判断是否为根结点 */
						if (cur == _root) {
							_root = cur->_right;
						}
						else
						{

							if (cur == father->_right)
							{
								father->_right = cur->_right;
							}
							else
							{
								father->_left = cur->_right;
							}
						}

						//删除
						delete cur;
						cur = nullptr;

					}
					else if(cur->_right==nullptr)//情况二：该节点没有右孩子
					{
						if (cur == _root) {
							_root = cur->_left;
						}
						else
						{

							if (cur == father->_right)
							{
								father->_right = cur->_left;
							}
							else
							{
								father->_left = cur->_right;
							}
						}

						//删除
						delete cur;
						cur = nullptr;

					}
					else /* 有两个节点，替换 */
					{
						Node* MinParNode = cur;
						Node* MinNode = cur->_right;

						//找到最小的孩子
						while (MinNode->_right)
						{
							MinParNode = MinNode;
							MinNode = MinNode->_right;
						}

						//交换要删除的数值
						swap(cur->_key, MinNode->_key);

                         //链接
						if (MinParNode->_left==MinNode)
						{
							MinParNode->_left = MinNode->_right;
						}
						else
						{
							MinNode->_right = MinNode->_right;
						}

						delete MinNode;
						MinNode = nullptr;

					}
					return true;
				}

				return false;
			}
		}



		//第二种写法
		Node* FindR(const K& key)
		{
			return _FindR(_root, key);
		}

		bool InsertR(const K& key,const V& value)
		{
			return _InsertR(_root,key, value);
		}

		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}


		private:
			//不用赋值的就直接搞
			Node* _root = nullptr;//根

			void _InOrder(Node * root)
			{
				//树为空或者到子叶
				if (root == nullptr)
				{
					return;//结束程序
				}

				_InOrder(root->_left);
				cout << root->_key << ":" << root->_value << endl;
				_InOrder(root->_right);

			}
		
			Node* _FindR(Node* root, const K& key)
			{
				if (root==nullptr)
				{
					return nullptr;
				}


				if (root->_key<key)
				{
					return _FindR(root->_right, key);
				}
				else if (root->_key>key)
				{
					return _FindR(root->_left, key);
				}
				else
				{
					//找到了
					return root;
				}

			}

			bool _InsertR(Node* root, const K& key, const V& value)
			{
				if (root==nullptr)
				{
					root = new Node(key,value);
					return true;
				}

				if (root->_key < key)
				{
					return _Insert(root->_right, key,value);
				}
				else if (root->_key > key)
				{
					return _Insert(root->_left, key,value);
				}
				else
				{
					
					return true;
				}

				
			}

			//&很妙，有了它就不用father
			bool _EraseR(Node*& root, const K& key)
			{
				if (root==nullptr)
				{
					return false;
				}



				if (root->_key < key)
				{
					return _EraseR(root->_right, key);
				}
				else if (root->_key > key)
				{
					return _EraseR(root->_left, key);
				}
				else
				{
					//记录要删的位置
					Node* del = root;
					
					//这里加了引用以后 
					//root代表父指向子的指针，就像链表一样，修改指针指向
					if (root->_right==nullptr)
					{
						root = root->_left;
					}
					else  if(root->_left==nullptr)
					{
						root = root->_right;
					}
					else
					{
						Node* rightMin = root->_right;
						while (rightMin->_left)
						{
							rightMin = rightMin->_left;
						}

						swap(root->_key, rightMin->_key);

						return _EraseR(root->_right, key);

					}

					delete del;
					return true;
				}

			}

			void Destroy(Node* root)
			{
				if (root == nullptr)
				{
					return;
				}

				Destroy(root->_right);
				Destroy(root->_left);

				delete root;
			}

			Node* Copy(Node* root)
			{
				if (root == nullptr)
				{
					return nullptr;
				}


				Node* newRoot = new Node(root->_key, root->_value);
				newRoot->_left = Copy(root->_left);
				newRoot->_right = Copy(root->_right);

				return newRoot;
			}


	};

	
	


	void Test1()
	{
		BSTree<int,string> t;
		t.Insert(1,"1");
		t.Insert(3,"3");
		t.Insert(9,"4");
		t.Insert(2,"5");


		t.InOrder();

		t.EraseR(1);

		t.InOrder();

	}


	void Test2()
	{
		BSTree<string, string> dict;
		dict.Insert("sort", "排序");
		dict.Insert("left", "左");
		dict.Insert("right", "右");
		dict.Insert("string", "字符串");

		string str;
		while (cin >> str)
		{
			auto ret = dict.FindR(str);
			if (ret)
			{
				cout << ret->_value << endl;
			}
			else
			{
				cout << "输入错误" << endl;
			}
		}
	}
}

int main()
{
	zl::Test1();
}